﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text
{
    //M 机关
    //# 墙(Wall)
    //S 起点(Start)
    //O 石头(stones)
    //T 终点(Target)
    public class LCP13
    {
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, 1, -1 };
        int n, m;
        public int MinimalSteps(string[] maze)
        {
            n = maze.Length;//迷宫的长度
            m = maze[0].Length;//迷宫的宽度
            // 机关 & 石头
            List<int[]> buttons = new List<int[]>();
            List<int[]> stones = new List<int[]>();
            // 起点x,y坐标 & 终点x,y坐标
            int sx = -1, sy = -1, tx = -1, ty = -1;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (maze[i][j] == 'M')
                    {
                        buttons.Add(new int[] { i, j });
                    }
                    if (maze[i][j] == 'O')
                    {
                        stones.Add(new int[] { i, j });
                    }
                    if (maze[i][j] == 'S')
                    {
                        sx = i;
                        sy = j;
                    }
                    if (maze[i][j] == 'T')
                    {
                        tx = i;
                        ty = j;
                    }
                }
            }
            int nb = buttons.Count;//机关的个数
            int ns = stones.Count;//石头的个数
            int[][] startDist = Bfs(sx, sy, maze);

            // 边界情况：没有机关
            if (nb == 0)
            {
                return startDist[tx][ty];
            }
            // 从某个机关到其他机关 / 起点与终点的最短距离。
            int[][] dist = new int[nb][];
            for (int i = 0; i < nb; i++)
            {
                dist[i] = new int[nb + 2];
                for (var j = 0; j < nb + 2; j++)
                {
                    dist[i][j] = -1;
                }
            }

            // 中间结果
            int[][][] dd = new int[nb][][];
            for (int i = 0; i < nb; i++)
            {
                int[][] d = Bfs(buttons[i][0], buttons[i][1], maze);
                dd[i] = d;
                // 从某个点到终点不需要拿石头
                dist[i][nb + 1] = d[tx][ty];
            }

            for (int i = 0; i < nb; i++)
            {
                int tmp = -1;
                for (int k = 0; k < ns; k++)
                {
                    int midX = stones[k][0], midY = stones[k][1];
                    if (dd[i][midX][midY] != -1 && startDist[midX][midY] != -1)
                    {
                        if (tmp == -1 || tmp > dd[i][midX][midY] + startDist[midX][midY])
                        {
                            tmp = dd[i][midX][midY] + startDist[midX][midY];
                        }
                    }
                }
                dist[i][nb] = tmp;
                for (int j = i + 1; j < nb; j++)
                {
                    int mn = -1;
                    for (int k = 0; k < ns; k++)
                    {
                        int midX = stones[k][0], midY = stones[k][1];
                        if (dd[i][midX][midY] != -1 && dd[j][midX][midY] != -1)
                        {
                            if (mn == -1 || mn > dd[i][midX][midY] + dd[j][midX][midY])
                            {
                                mn = dd[i][midX][midY] + dd[j][midX][midY];
                            }
                        }
                    }
                    dist[i][j] = mn;
                    dist[j][i] = mn;
                }
            }

            // 无法达成的情形
            for (int i = 0; i < nb; i++)
            {
                if (dist[i][nb] == -1 || dist[i][nb + 1] == -1)
                {
                    return -1;
                }
            }

            // dp 数组， -1 代表没有遍历到
            var temp = 1 << nb;
            int[][] dp = new int[temp][];
            for (int i = 0; i < temp; i++)
            {
                dp[i] = new int[nb];
                for (var j = 0; j < nb; j++)
                {
                    dp[i][j] = -1;
                }
            }
            for (int i = 0; i < nb; i++)
            {
                dp[1 << i][i] = dist[i][nb];
            }

            // 由于更新的状态都比未更新的大，所以直接从小到大遍历即可
            for (int mask = 1; mask < (1 << nb); mask++)
            {
                for (int i = 0; i < nb; i++)
                {
                    // 当前 dp 是合法的
                    if ((mask & (1 << i)) != 0)
                    {
                        for (int j = 0; j < nb; j++)
                        {
                            // j 不在 mask 里
                            if ((mask & (1 << j)) == 0)
                            {
                                int next = mask | (1 << j);
                                if (dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dist[i][j])
                                {
                                    dp[next][j] = dp[mask][i] + dist[i][j];
                                }
                            }
                        }
                    }
                }
            }

            int ret = -1;
            int finalMask = (1 << nb) - 1;
            for (int i = 0; i < nb; i++)
            {
                if (ret == -1 || ret > dp[finalMask][i] + dist[i][nb + 1])
                {
                    ret = dp[finalMask][i] + dist[i][nb + 1];
                }
            }

            return ret;
        }

        public int[][] Bfs(int x, int y, String[] maze)
        {
            int[][] ret = new int[n][];
            for (int i = 0; i < n; i++)//初始化
            {
                ret[i] = new int[m];
                for (var j = 0; j < m; j++)
                {
                    ret[i][j] = -1;
                }
            }
            ret[x][y] = 0;//赋值起点
            Queue<int[]> queue = new Queue<int[]>();
            queue.Enqueue(new int[] { x, y });
            while (queue.Count > 0)
            {
                int[] p = queue.Dequeue();
                int curx = p[0], cury = p[1];
                for (int k = 0; k < 4; k++)
                {
                    int nx = curx + dx[k], ny = cury + dy[k];
                    if (InBound(nx, ny) && maze[nx][ny] != '#' && ret[nx][ny] == -1)
                    {
                        ret[nx][ny] = ret[curx][cury] + 1;
                        queue.Enqueue(new int[] { nx, ny });
                    }
                }
            }
            return ret;
        }

        public bool InBound(int x, int y)
        {
            return x >= 0 && x < n && y >= 0 && y < m;
        }
    }
}
